class Solution(object):
    def splitArray(self, nums, m):
        """
        :type nums: List[int]
        :type m: int
        :rtype: int
        """
        n = len(nums)
        left = min(nums)
        right = sum(nums)

        def search(value):
            count = 0
            max_value = - 1
            i = 0
            now_value = 0
            while i < n - (m - 1 - count) and count < m - 1:
                if now_value + nums[i] <= value:
                    now_value += nums[i]
                    i += 1
                else:
                    max_value = max(max_value, now_value)
                    now_value = 0
                    count += 1
            if count == m - 1:
                max_value = max(max_value, sum(nums[i:]))
            else:
                max_value = max(max_value, now_value)
                count += 1
                for j in range(i, n):
                    max_value = max(max_value, nums[j])
            return max_value

        search(36)
        while left < right:
            mid = (left + right) // 2
            value = search(mid)
            if value <= mid:
                right = value
            else:
                left = mid + 1
        return left


data = Solution()
# nums = [7, 2, 5, 10, 8]
# m = 2
# print(data.splitArray(nums, m))
# nums = [1, 2, 3, 4, 5]
# m = 1
# print(data.splitArray(nums, m))
# nums = [1, 4, 9]
# m = 1
# print(data.splitArray(nums, m))
nums = [2, 16, 14, 15]
m = 2
print(data.splitArray(nums, m))
